Appendix A, which is a part of the present disclosure, is a listing of software code for embodiments of components of this invention, which are described more completely below.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
This invention relates to fingerprint verification. More particularly, this invention relates to methods for matching fingerprint templates and structures thereof.
Biometric identification is used to verify the identity of a person by digitally measuring selected features of some physical characteristic and comparing those measurements with those filed for the person in a reference database, or sometimes on a smart card carried by the person. Physical characteristics that are being used include fingerprints, voiceprints, the geometry of the hand, the pattern of blood vessels on the wrist and on the retina of the eye, the topography of the iris of the eye, facial patterns and the dynamics of writing a signature and typing on a keyboard.
The fingerprint is one of the most widely used physical characteristics in biometric identification. Fingerprints are utilized as the most reliable means to identify individuals because of two outstanding characteristics; namely that they remain unchanged all through life and differ from individual to individual. Fingerprints consist of raised friction ridges of skin separated by recessed valleys of skin. Fingerprint xe2x80x9cminutiaexe2x80x9d are conventionally defined as ridge endings or ridge bifurcations where a ridge splits into two ridges.
Since the matching of a fingerprint as an image can require large file capacity to store the measured and referenced features and complex computation to match measured features with reference features, fingerprint identification is carried out using the positional relationship of features or minutiae that are extracted from the fingerprint image. The minutiae representing a fingerprint image are digitized and stored in a digital memory, which may be a read-only memory, magnetic tape, or the like. A fingerprint digitized in this manner may be compared with reference fingerprints stored in the memory. For the comparison to work, the reference fingerprint and the measured fingerprint must be extracted, characterized, and digitized so that the fingerprint templates contain the same information and have the same format.
One application of fingerprint identification is to use the fingerprint to unlock a smart card which often contains encrypted information. Presently, a PIN (personal identification number) is required to be entered by the user before the encrypted information can be extracted from the smart card and used. The use of a PIN has many drawbacks. For example, the accounting or card issuing organization faces significant administrative cost in handling the secret codes and the card holders have to memorize the secret codes.
Some privacy laws, for example, the privacy laws in Europe, require sensitive information such as a reference fingerprint template to be stored on the smart card in a way that it cannot leave the card without first unlocking the card with a PIN. Therefore, for a fingerprint matching scheme to be practical in Europe, the fingerprint template matching algorithm must be executed by a microprocessor in the smart card. Otherwise, the smart card must be unlocked by some other mechanism, such as a PIN, before the reference fingerprint template can be read. The difficulty of executing conventional fingerprint template matching algorithm on a smart card is mainly due to the limited computational capabilities and memory of a conventional smart card. For example, a conventional smart card typically has less than 512 bytes of RAM (with 256 bytes being typical) and between 1 Kilobyte and 16 Kilobytes of memory. An 8-bit RISC (reduced instruction set computer) microprocessor has a speed between 1 MegaHertz to 10 MegaHertz which is quite slow given the magnitude of the computations required to complete a comparison between a measured fingerprint and a reference fingerprint. In effect, the hardware constraints prevent the use of fingerprint to unlock data from smart cards.
In addition to hardware constraints, another important design criterion is cost. U.S. Pat. No. 4,582,985 (hereinafter, the ""985 patent) entitled xe2x80x9cData Carrierxe2x80x9d, issued Apr. 15, 1986, to Bxc3x6Lofberg and hereby incorporated by reference in its entirety, describes a data carrier of a card type. According to the ""985 patent, the data carrier includes a fingerprint verification device for carrying out the verification process. The verification device includes a sensor device for sensing a finger tip of the owner and obtaining the corresponding finger print line information. A specialized smart card must be used to accommodate the sensor device since a conventional smart card does not provide such accommodations. In addition, since the fingerprint template generation, storage, and comparison are done at the data carrier, the microprocessor of a conventional smart card is not adequate. Hence, a specialized smart card having a more capable processor must be used, thereby increasing cost.
Therefore, what is needed are systems and fingerprint template matching algorithms that can be executed by a microprocessor with low memory and low computational capacities, thereby keeping the cost of the smart card at an acceptable level.
In accordance with the present invention, a smart card verification system and a fingerprint template matching algorithm are provided. The fingerprint template matching algorithm is capable of being executed by a microprocessor with low memory and low computational capacities.
In one embodiment of this invention, a reference fingerprint template and a measured fingerprint template are generated from a reference fingerprint image and a fingerprint image to be verified, respectively. Each template comprises a plurality of data chunks, each data chunk representing a minutia and comprising a location, a minutia angle and a neighborhood. In one embodiment, the location is represented by two coordinates (xj, yj), the coordinates having a center point (0,0) at the upper left hand corner. The minutia angle xcex8j is the angle between the x-axis and a line tangential to the ridge line at the minutia. In one embodiment, each coordinate and the minutia angle are quantized to a selected number of bits. In general, the amount of quantization is a function of the available memory and the degree of accuracy desired.
The neighborhood is made up of a predetermined number of neighbor minutiae which are selected for every minutia extracted from a fingerprint image. Each neighbor minutia is characterized by three positional parameters with respect to the selected minutia. The positional parameters include a distance and two angles.
In one embodiment, an optional neighborhood boundary is drawn around a randomly-selected minutia. In one embodiment, if the number of neighbor minutiae within the neighborhood boundary is less than the predetermined number, all neighbor minutiae within the neighborhood boundary are selected. In another embodiment, a predetermined number of the closest neighboring minutiae are selected. In yet another embodiment, a predetermined number of neighbor minutiae giving the best spread around the randomly selected minutia are selected. In one embodiment, the minutiae having the farthest distance from each other are selected. In another embodiment, minutiae that are very close, e.g., less than approximately 10 pixels, to each other are not selected. In another embodiment, an arbitrary one of the very close minutiae is selected. In one embodiment, a quadrant is arbitrarily drawn using the randomly-selected minutia as the center point and a predetermined number of minutiae are selected from each quadrant.
An x-axis is drawn in the direction of the line tangential to the ridge at the randomly-selected minutia. A y-axis, perpendicular to the x-axis, is drawn. The x-axis and the y-axis intersect at the randomly-selected minutia. Hence, the randomly-selected minutia now has a position of (0,0) and is designated as the xe2x80x9ccenter minutia.xe2x80x9d A first line is drawn between the center minutia and one of its neighbor minutiae. The first line has a distance di which is one of the positional parameters representing the neighbor minutia. An angle xcfx86i between the first line and the x-axis is the second positional parameter representing the neighbor minutia. A second line is then drawn from the neighbor minutia to intersect the x-axis, in the direction of the line tangential to the ridge of neighbor minutia. The angle xcfx86i between the x-axis and the second line is the third positional parameter representing the neighbor minutia.
In one embodiment, each positional parameter is quantized to a selected number of bits. For example, each angle xcfx86i and xcfx86i is quantized to six bits and the distance di is quantized to five bits.
A data chunk from each fingerprint template is loaded into a random access memory (RAM) to be compared. In one embodiment, the data chunks are sorted, but such sorting is optional. In one embodiment, the data chunks are sorted in accordance to their x-coordinates. In another embodiment, the data chunks are sorted in accordance to their y-coordinates. In one embodiment, the data chunks in the reference template are sorted. In another embodiment, the data chunks in the measured template are sorted. In yet another embodiment, both the measured template and the reference template are sorted.
Each of the characterization parameters, i.e., location, minutia angle, and neighborhood, of the measured data chunk to be compared is compared with its respective counterpart in the reference data chunk. The order of the comparison may be varied. For example, the location parameter in the x-coordinates of the measured minutiae are compared first to the corresponding x-coordinates of the reference minutiae. In another embodiment, location parameter in the y-coordinates of the measured minutiae are compared first to the corresponding y-coordinates of the reference minutiae. In one embodiment, the comparison is straight subtraction. If the difference for a parameter pair is equal to or is less than a respective predetermined tolerance, the parameters match. If all of the parameters match, the data chunks match. On the other hand, if one of the parameters fail to match, the data chunks do not match and the next set of data chunks are compared.
The data chunk comparison begins with the first reference data chunk and the first measured data chunk and terminates if the predetermined number of data chunk matches have been reached (i.e., the templates match) or if all of the data chunk combinations have been compared. In one embodiment, if the first reference data chunk and the first measured data chunk do not match, the next measured data chunk is loaded into the RAM to be compared with the first reference data chunk. The process continues until all the measured data chunks in the measured fingerprint template have been compared. The next reference data chunk and the first measured data chunk are then loaded into the RAM to be compared. The process continues until all the reference data chunks have been compared. In another embodiment, if the first reference data chunk does not match the first measured data chunk, the second reference data chunk is loaded into the RAM to be compared with the first measured data chunk. The process continues until all of the reference chunks have been compared. The second measured data chunk and the first reference data chunk are then loaded into the RAM to be compared. The process continues until all of the measured data chunks have been compared.
In one embodiment, where the data chunks are sorted, the comparison between a reference data chunk and the remaining uncompared measured data chunks is terminated if the difference between the reference data chunk and the measured data chunk exceeds the tolerance. In one embodiment, the next comparison starts with the next reference data chunk and the first matching measured data chunk.
In the alternative embodiment, the comparison between a measured data chunk and the remaining uncompared reference data chunks is terminated if the difference between the measured data chunk and the reference data chunk exceeds the tolerance. In one embodiment, the next comparison starts with the next reference data chunk and the first matching measured data chunk.
In one embodiment, the neighbor minutiae in a neighborhood are sorted by distance di. The neighborhood comparison starts with the first neighbor in the reference neighborhood and the first neighbor in the measured neighborhood and terminates when the predetermined neighbor matches are reached (i.e., the neighborhoods match) or when all of the neighbor combinations have been compared. Each reference""s positional parameter is compared with its corresponding measured positional parameter. In one embodiment, the comparison is done with straight subtraction. If the difference meets a predetermined tolerance, the parameters match. If all of the positional parameters in the neighbor minutia match, the neighbor minutiae match. If one of the positional parameters does not match, the neighbor minutiae do not match.
In one embodiment, the reference fingerprint template is stored in a static memory in a smart card and the fingerprint template matching algorithm is executed in a microprocessor in the smart card. In one embodiment, the reference fingerprint template is generated and stored at a smart card reader.
The above-described fingerprint template matching algorithm may be executed by a microprocessor with low memory and low computational capacities because the matching algorithm does not require computational intensive operations and does not require comparisons that exceeds 8 bits.